#include <iostream>

#include <vector>
#include <algorithm>

using namespace std;

/*
* 这里我考虑的子序列是连续的，但是题目中子序列的定义可以不连续
 */
// int getLongestNonDecreasingSubsequenceLength(vector<int> a) {
//     int n = a.size();
//     vector<int> dp(n, 0);
//     dp[0] = 1;
//     for (int i = 1; i < n; i++) {
//         dp[i] = 1;
//         for (int j = i; j < n; j++) {
//             if (a[j] <= a[i]) {
//                 dp[i]++;
//             } else 
//                 break;
//         }
//         dp[i] = max(dp[i], dp[i - 1]);
//     }

//     return dp[n - 1];
// }

int getLongestNonDecreasingSubsequenceLength_1(vector<int> a) {
    int n = a.size();
    if (n == 0) return 0;
    // 思路一：O(n^2) 动态规划
    // d[i] 表示以 a[i] 结尾的最长不下降子序列长度
    vector<int> d(n, 1);
    int ans = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] <= a[i]) {
                d[i] = max(d[i], d[j] + 1);
            }
        }
        ans = max(ans, d[i]);
    }
    return ans;
}

int getLongestNonDecreasingSubsequenceLength_2(vector<int> input) {
    // 按文档“思路二”的实现（数组+索引追踪），使用 upper_bound 求非下降子序列
    int n = static_cast<int>(input.size());
    if (n == 0) return 0;

    // 使用 1-based 索引，保持与文档一致
    vector<int> a(n + 1), d(n + 1), di(n + 1), pre(n + 1), res(n + 1);
    for (int i = 1; i <= n; ++i) a[i] = input[i - 1];

    int ans = 0; // 当前已构造的最长长度
    for (int i = 1; i <= n; ++i) {
        // upper_bound 实现“非下降（<=）”的耐心排序变体
        int tmp = static_cast<int>(upper_bound(d.begin(), d.begin() + ans, a[i]) - d.begin());
        pre[i] = tmp ? di[tmp - 1] : -1; // 记录前驱索引
        d[tmp] = a[i];
        di[tmp] = i; // 记录该长度末尾位置的原数组索引
        if (tmp == ans) ++ans;
    }

    // 可选：重建一个最长非下降子序列（不影响函数返回值）
    // for (int k = ans, i = di[ans - 1]; k; --k) {
    //     res[k] = a[i];
    //     i = pre[i];
    // }

    return ans;
}

void test11() {
    // 测试用例1：基础示例
    vector<int> a = {1, 2, 4, 3, 5};
    int result1 = getLongestNonDecreasingSubsequenceLength_1(a);
    cout << "测试11 - a: ";
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    cout << "最长不下降子序列长度: " << result1 << endl;
    cout << "预期结果: 4" << endl;
    cout << (result1 == 4 ? "✓ 通过" : "✗ 失败") << endl << endl;
}

void test21() {
    // 测试用例1：基础示例
    vector<int> a = {1, 2, 4, 3, 5};
    int result1 = getLongestNonDecreasingSubsequenceLength_2(a);
    cout << "测试21 - a: ";
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    cout << "最长不下降子序列长度: " << result1 << endl;
    cout << "预期结果: 4" << endl;
    cout << (result1 == 4 ? "✓ 通过" : "✗ 失败") << endl << endl;
}

int main() {
    cout << "==================================================" << endl;
    cout << "最长不下降子序列 (LNDS) 算法测试" << endl;
    cout << "==================================================" << endl << endl;
    
    // 运行所有测试
    test11();
    test21();
    
    
    cout << "==================================================" << endl;
    cout << "所有测试完成！" << endl;
    cout << "==================================================" << endl;
    
    return 0;
}
